#include "ad_construct.h"
#include <cstdio>
#include <cstring>
#include <algorithm>

inline int get_length(int plen, input_data & INPUT){
  return (2 * plen * INPUT.beta.num + INPUT.beta.p + 2 * INPUT.beta.denum - 1) / (2 * INPUT.beta.denum);
}

bool has_bad_suffix(const char * buff, int len, int zquant_letters[MAX_WORD_LENGTH][MAX_ALPH_SIZE], dfa * DFA, input_data & INPUT){
  if (INPUT.beta.num % INPUT.beta.denum == 0 && INPUT.beta.p == 0){
    return DFA->bad_suffix_trie(buff, len);
  }
  else if (INPUT.beta.intval() == 1 && INPUT.power_type == STRONG){
    return DFA->bad_suffix_trie(buff, len) || has_bad_suffix_dumb(buff, len, zquant_letters, INPUT);
  }
  else{
    return has_bad_suffix_dumb(buff, len, zquant_letters, INPUT);
  }
}

bool has_bad_suffix_dumb(const char * buff, int len, int zquant_letters[MAX_WORD_LENGTH][MAX_ALPH_SIZE], input_data & INPUT){
  int cnt[MAX_ALPH_SIZE];
  memset(cnt, 0, sizeof(int) * MAX_ALPH_SIZE);
  int tail = len, head = len-1;
  while (head >= 0){
    tail--;
    char c = buff[tail] - 'a';
    if (tail == len-1) cnt[c]--;
    else cnt[c] -= 2;
    while (cnt[c] < 0){
      head--;
      if (head < 0) break;
      cnt[buff[head] - 'a']++;
    }
    if (head >= 0){
      int zhead = head;
      while (zhead >= 0){
        int hlen = tail - zhead;
        int tlen = len - tail;
        if (get_length(hlen, INPUT) > hlen * INPUT.beta.intval() + tlen) break;
        if (INPUT.power_type == WEAK && INPUT.beta.intval() == 1) return true;
        // ZQUANT_LETTERS GOES INTO WORK HERE!!!!
        if (check_head_tail(buff, len, zhead, tail, zquant_letters, INPUT)) return true;
        zhead--;
      }
    }
  }
  return false;
}

bool check_head_tail(const char * buff, int len, int head, int tail, int zquant_letters[MAX_WORD_LENGTH][MAX_ALPH_SIZE], input_data & INPUT){
  int hlen = tail - head;
  int tlen = len - tail;
  if (hlen * INPUT.beta.intval() + tlen > len) return false;
  int tail_quant[MAX_ALPH_SIZE];
  int head_quant[MAX_ALPH_SIZE];
  int qmax[MAX_ALPH_SIZE];
  for (int j=0; j<INPUT.ALPH_SIZE; j++){
    tail_quant[j] = zquant_letters[len][j] - zquant_letters[tail][j];
    head_quant[j] = zquant_letters[head + hlen][j] - zquant_letters[head][j];
    if (head_quant[j] < tail_quant[j]) return false;
    qmax[j] = zquant_letters[head + tlen][j] - zquant_letters[head][j];
    if (INPUT.beta.intval()== 1 && INPUT.power_type == STRONG){
      if (qmax[j] != tail_quant[j]) return false;
    }
  }
  for (int i=1; i<INPUT.beta.intval(); i++){
    for (int j=0; j<INPUT.ALPH_SIZE; j++){
      int cquant;
      // Each part is a perm of "head"
      cquant = zquant_letters[head - i * hlen + hlen][j] - zquant_letters[head - i * hlen][j];
      if (cquant != head_quant[j]) return false;
      cquant = zquant_letters[head - i * hlen + tlen][j] - zquant_letters[head - i * hlen][j];
      if (cquant > qmax[j]) qmax[j] = cquant;
      if (i == INPUT.beta.intval() - 1 && INPUT.power_type == STRONG){
        if (cquant != tail_quant[j]) return false;
      }
    }
  }
  if (INPUT.power_type == MODERATE){
    for (int j=0; j<INPUT.ALPH_SIZE; j++){
      if (qmax[j] < tail_quant[j]) return false;
    }
  }
  return true;
}

int root_length;
char root_letnum;
char root_letters[MAX_ALPH_SIZE];
int root_freqs[MAX_ALPH_SIZE];
char cur_letters[MAX_ALPH_SIZE];
int cur_freqs[MAX_ALPH_SIZE];

// quant_letters[i][j] - how many letters "j" we have in the prefix of length "i";
int quant_letters[MAX_WORD_LENGTH][MAX_ALPH_SIZE];

void build_words(char* cword, int clen, int nlen, int mlen, char letnum, dfa * DFA, input_data & INPUT){
  if (clen >= nlen && clen <= mlen){
    bool should_add;
    if (INPUT.power_type == WEAK){
      should_add = true;
    }
    else if (INPUT.power_type == STRONG){
      int mod = clen % root_length;
      int i;
      // check that the last "mod" symbols are permutations of the first "mod"
      for (i=0; i<INPUT.ALPH_SIZE; i++){
        if (quant_letters[clen][i] - quant_letters[clen-mod][i] != quant_letters[mod][i]) break;
      }
      should_add = (i == INPUT.ALPH_SIZE);
    }
    else if (INPUT.power_type == MODERATE){
      int mod = clen % root_length;
      int i;
      // check that in the last "mod" we have not greater symbols of each kind
      // than in the first "mod" symbols of each part
      for (i=0; i<INPUT.ALPH_SIZE; i++){
        int hmuch = quant_letters[clen][i] - quant_letters[clen-mod][i];
        int maxq = 0;
        for (int j=0; j<INPUT.beta.intval(); j++){
          int curq = quant_letters[root_length * j + mod][i] - quant_letters[root_length * j][i];
          if (curq > maxq) maxq = curq;
        }
        if (hmuch > maxq) break;
      }
      should_add = (i == INPUT.ALPH_SIZE);
    }
    if (should_add){
      if (!(DFA->add_word(cword))){
        INPUT.dump("ERROR! Insufficient DFA size!\n");
        exit(1);
      }
      return;
    }
  }
  if (clen == mlen || has_bad_suffix(cword, clen, quant_letters, DFA, INPUT)){
    return;
  }
  char t_letters[MAX_ALPH_SIZE];
  int t_freqs[MAX_ALPH_SIZE];
  if (clen % root_length == 0){
    letnum = root_letnum;
    for (int i=0; i<INPUT.ALPH_SIZE; i++){
      t_letters[i] = cur_letters[i];
      cur_letters[i] = root_letters[i];
      t_freqs[i] = cur_freqs[i];
      cur_freqs[i] = root_freqs[i];
    }
  }
  for (char c=0; c<letnum; c++){
    cword[clen] = cur_letters[c];
    cword[clen + 1] = 0;
    bool ok = false;
    for (char j=0; j<INPUT.ALPH_SIZE; j++){
      quant_letters[clen + 1][j] = quant_letters[clen][j];
    }
    quant_letters[clen + 1][cword[clen] - 'a']++;
    if (clen < nlen - 1) ok = !has_bad_suffix(cword, clen + 1, quant_letters, DFA, INPUT);
    else ok = !has_bad_suffix(cword + 1, clen, &(quant_letters[1]), DFA, INPUT);
    if (ok){
      cur_freqs[c]--;
      bool swapped = false;
      if (cur_freqs[c] == 0){
        swapped = true;
        std::swap(cur_freqs[c], cur_freqs[letnum-1]);
        std::swap(cur_letters[c], cur_letters[letnum-1]);
        build_words(cword, clen + 1, nlen, mlen, letnum - 1, DFA, INPUT);
      }
      else{
        build_words(cword, clen + 1, nlen, mlen, letnum, DFA, INPUT);
      }
      if (swapped){
        std::swap(cur_freqs[c], cur_freqs[letnum-1]);
        std::swap(cur_letters[c], cur_letters[letnum-1]);
      }
      cur_freqs[c]++;
    }
    for (char j=0; j<INPUT.ALPH_SIZE; j++){
      quant_letters[clen + 1][j] = 0;
    }
  }
  cword[clen] = 0;
  if (clen % root_length == 0){
    for (int i=0; i<INPUT.ALPH_SIZE; i++){
      cur_letters[i] = t_letters[i];
      cur_freqs[i] = t_freqs[i];
    }
  }
}

void handle_root(const char* cword, int clen, char maxlet, dfa * DFA, input_data & INPUT){
  int i;
  char thword[MAX_WORD_LENGTH + 1];

  root_length = clen;
  root_letnum = maxlet-'a'+1;

  memset(root_freqs, 0, sizeof(int) * MAX_ALPH_SIZE);

  for (char ch='a'; ch<=maxlet; ch++){
    root_letters[ch-'a'] = ch;
  }

  // Copy the root to thword
  for (i=0; i<root_length; i++){
    thword[i] = cword[i];
    root_freqs[cword[i]-'a']++;
  }
  thword[clen] = 0;
  if (clen > MAX_WORD_LENGTH){
    INPUT.dump("Achtung! The length of the word is too small!");
    exit(1);
  }

  // The length we need
  int nlen = get_length(clen, INPUT);
  // Maximal possible length of forbidden word for strict powers
  int maxlen;
  if (INPUT.power_type == WEAK){
    maxlen = nlen;
  }
  else{
    maxlen = (nlen + root_length - 1) / root_length * root_length;
  }

  build_words(thword, clen, nlen, maxlen, root_letnum, DFA, INPUT);  
}

i64 construct_antidictionary(input_data & INPUT, words_queue * WORDS_QUEUE, dfa * DFA){
  i64 max_words_queue_size = 0;
  long long marker_pos;

  WORDS_QUEUE->push_marker(marker_pos); // sets marker_pos to 0
  WORDS_QUEUE->push_symbol('a');

  int i;
  int clen = 0;
  char bad_word[MAX_WORD_LENGTH + 1];

  while (! WORDS_QUEUE->is_empty()){
    if (WORDS_QUEUE->is_index(marker_pos)){
      if (clen < INPUT.ROOT_LENGTH){
        clen++;
        WORDS_QUEUE->push_marker(marker_pos);
        WORDS_QUEUE->pop_symbol();
        continue;
      }
      else break;
    }
    
    // there is a word in the queue starting at qbeg with (length = clen)
    char maxlet = 'a';
    for (int j=0; j<INPUT.ALPH_SIZE; j++){
      quant_letters[0][j] = 0;
    }
    for (i=0; i<clen; i++){
      bad_word[i] = WORDS_QUEUE->pop_symbol() + 'a';
      if (bad_word[i] > maxlet){
        maxlet = bad_word[i];
      }
      for (int j=0; j<INPUT.ALPH_SIZE; j++){
        quant_letters[i+1][j] = quant_letters[i][j];
      }
      quant_letters[i+1][bad_word[i]-'a']++;
    }
    bad_word[clen] = 0;

    handle_root(bad_word, clen, maxlet, DFA, INPUT);

    if (clen < INPUT.ROOT_LENGTH){
      char ch;
      for (ch='a'; ch<=maxlet; ch++){
        bad_word[clen] = ch;
        bad_word[clen+1] = 0;
        for (int j=0; j<INPUT.ALPH_SIZE; j++){
          quant_letters[clen+1][j] = quant_letters[clen][j];
        }
        quant_letters[clen+1][ch-'a']++;
        if (!has_bad_suffix(bad_word, clen+1, quant_letters, DFA, INPUT)){
          if (!WORDS_QUEUE->push_word(bad_word)){
            INPUT.dump("ERROR! Insufficient words queue size!\n");
            exit(1);
          }
        }
      }
      if (maxlet-'a'+1 < INPUT.ALPH_SIZE){
        bad_word[clen] = maxlet+1;
        bad_word[clen+1] = 0;
        if (!WORDS_QUEUE->push_word(bad_word)){
            INPUT.dump("ERROR! Insufficient words queue size!\n");
            exit(1);
          }
      }
    }
    i64 cwqsz = WORDS_QUEUE->get_number_of_letters();
    if (cwqsz > max_words_queue_size){
      max_words_queue_size = cwqsz;
    }
  }
  delete WORDS_QUEUE;

  return max_words_queue_size;
}
